//给你一个 n x n 的网格 grid ，代表一块樱桃地，每个格子由以下三种数字的一种来表示： 
//
// 
// 0 表示这个格子是空的，所以你可以穿过它。 
// 1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。 
// -1 表示这个格子里有荆棘，挡着你的路。 
// 
//
// 请你统计并返回：在遵守下列规则的情况下，能摘到的最多樱桃数： 
//
// 
// 从位置 (0, 0) 出发，最后到达 (n - 1, n - 1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为 0 或者 1 的格子）；
// 
// 当到达 (n - 1, n - 1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子； 
// 当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为 0 ）； 
// 如果在 (0, 0) 和 (n - 1, n - 1) 之间不存在一条可经过的路径，则无法摘到任何一个樱桃。 
// 
//
// 
//
// 示例 1： 
// 
// 
//输入：grid = [[0,1,-1],[1,0,-1],[1,1,1]]
//输出：5
//解释：玩家从 (0, 0) 出发：向下、向下、向右、向右移动至 (2, 2) 。
//在这一次行程中捡到 4 个樱桃，矩阵变成 [[0,1,-1],[0,0,-1],[0,0,0]] 。
//然后，玩家向左、向上、向上、向左返回起点，再捡到 1 个樱桃。
//总共捡到 5 个樱桃，这是最大可能值。
// 
//
// 示例 2： 
//
// 
//输入：grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// n == grid.length 
// n == grid[i].length 
// 1 <= n <= 50 
// grid[i][j] 为 -1、0 或 1 
// grid[0][0] != -1 
// grid[n - 1][n - 1] != -1 
// 
//
// Related Topics 数组 动态规划 矩阵 👍 444 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2024-05-07 11:27:12
 * @description 741.摘樱桃
 */
public class CherryPickup{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 CherryPickup fun=new CherryPickup();
	 	 Solution solution = fun.new Solution();
		 System.out.println(solution.cherryPickup(new int[][]{{1, 1, -1}, {1, 0, -1}, {1, 1, 1}}));
//		 System.out.println(solution.cherryPickup(new int[][]{{1}}));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 int [] dx={1,0};
		 int [] dy={0,1};
		 int m=0;
		 Map<Integer, List<Integer[]>> map=new HashMap<>();
		 //超时咯，且两次贪心最优不等于全局最优
    public int cherryPickup1 (int[][] grid) {
		if(grid.length==1) return grid[0][0]==1?1:0;
		int res=0;
		List<Integer[]> path=new ArrayList<>();
		path.add(new Integer[]{0,0});
		dfs(grid,0,0,grid[0][0],path);
		if(m==0) return 0;
		dx= new int[]{-1, 0};
		dy= new int[]{0, -1};
		res+=m;
		for (Integer[] integers : map.get(m)) {
			grid[integers[0]][integers[1]]=0;
		}
		m=0;
		map.clear();
		path.clear();
		path.add(new Integer[]{grid.length-1,grid[0].length-1});
		dfs(grid,grid.length-1,grid[0].length-1,grid[grid.length-1][grid[0].length-1],path);
		res+=m;
		return res;
    }
	public void dfs(int [][]grid,int x,int y,int c,List<Integer[]> path){
		if((x==grid.length-1)&&(y==grid[0].length-1)&& path.size()!=1){
			if(c>m){
				map.put(c,new ArrayList<>(path));
				m=c;
			}
			return ;
		}
		if((x==0)&&(y==0)&& path.size()!=1){
			if(c>m){
				map.put(c,new ArrayList<>(path));
				m=c;
			}
			return ;
		}
		for (int i = x; i < grid.length; i++) {
			for (int j = y; j < grid[0].length; j++) {
				for (int k = 0; k < 2; k++) {
					int nx=x+dx[k];
					int ny=y+dy[k];
					if(!isOut(grid,nx,ny)){
						path.add(new Integer[]{nx,ny});
						c+=grid[nx][ny];
						dfs(grid,nx,ny,c,path);
						path.remove(path.size()-1);
						c-=grid[nx][ny];
					}
				}
			}
		}
	}
	public boolean isOut(int [][] grid,int x,int y){
		return x>=grid.length||x<0||y>=grid[0].length||y<0||grid[x][y]==-1;
	}

	/*走到终点再走到起点，等价于两个人同时从起点走到终点
	两个人的状态要互相约束，因此用一个三维数组f[k][x1][x2]表示状态
	两个人同步，因此走的步数都是k，
	x1,x2表示纵坐标，都从0开始，则k-x1,k-x2,可以表示横坐标
	即x1+y1=x2+y2=k,当x1=x2时，必有y2=y2，即到达一个位置
	都往右，则f[k-1][x1][x2]，
	A下，B右f[k-1][x1-1][x2]
	A右，B下f[k-1][x1][x2-1]
	都往下f[k-1][x1-1][x2-1]
	取四种情况的最大值，加上对应格子的值grid[x1][k-x1]、grid[x2][k-x2]
	就得到f[k][x1][x2]，如果x1=x2.则只需要加一个
	最后结果为max(f[2n-2][n-1][n-1],0)
	边界为x1,x2,k-x1,k-x2,grid[x1][k-x1]grid[x2][k-x2]中的一个小于0
	或者到达终点dfs(0,0,0)=grid[0][0]

	同时利用记忆化搜索来保存值优化时间
	* */

	public int cherryPickup2(int[][] grid) {
		int n=grid.length;
		int [][][]memo=new int[n*2-1][n][n];
		for (int[][] m : memo) {
			for (int[] r : m) {
				Arrays.fill(r,-1);
			}
		}
		return Math.max(0,dfs(n-1,n-1,n*2-2,grid,memo));
	}


	public int dfs(int x1,int x2,int k,int [][] grid,int [][][]memo){
		if(x1<0||x2<0||k<x1||k<x2||grid[x1][k-x1]<0||grid[x2][k-x2]<0){
			return Integer.MIN_VALUE;
		}
		if(k==0){  //走完了，x1=x2=0
			return grid[0][0];
		}
		if(memo[k][x1][x2]!=-1){//没有计算过
			return memo[k][x1][x2];
		}
		int res=Math.max(
				Math.max(dfs(x1,x2,k-1,grid,memo),dfs(x1-1,x2,k-1,grid,memo)),
				Math.max(dfs(x1,x2-1,k-1,grid,memo),dfs(x1-1,x2-1,k-1,grid,memo))
		)+grid[x1][k-x1]+(x1!=x2?grid[x2][k-x2]:0);
		memo[k][x1][x2]=res;//记忆化
		return res;
	}
	//迭代
	public int cherryPickup3(int[][] grid) {
		int n = grid.length;
		//在左和上加一排表示状态，坐标全部右下一位，f[k][0][]或f[k][][0]出界
		int[][][] f = new int[n * 2 - 1][n + 1][n + 1];
		for (int[][] m : f) {
			for (int[] r : m) {
				Arrays.fill(r, Integer.MIN_VALUE);
			}
		}
		f[0][1][1] = grid[0][0];
		// i+j=t,0<=i<=n-1,且0<=j<=n-1
		//联立得max(t-n+1,0)<=j<=min(t,n-1),k同理
		for (int t = 1; t < n * 2 - 1; t++) {
			for (int j = Math.max(t - n + 1, 0); j <= Math.min(t, n - 1); j++) {
				if (grid[t - j][j] < 0) continue;
				for (int k = j; k <= Math.min(t, n - 1); k++) {
					if (grid[t - k][k] < 0) continue;
					f[t][j + 1][k + 1] = Math.max(Math.max(f[t - 1][j + 1][k + 1], f[t - 1][j + 1][k]), Math.max(f[t - 1][j][k + 1], f[t - 1][j][k])) +
							grid[t - j][j] + (k != j ? grid[t - k][k] : 0);
				}
			}
		}
		return Math.max(f[n * 2 - 2][n][n], 0);
	}

	//空间优化，因为T一定，所以可以降一维
	//但是要倒序，因为更新状态时，f[t-1][j][k]和f[t][j][k]都写为了f[j][k]
	//倒序可以保证t-1轮的没有被覆盖
	public int cherryPickup(int[][] grid) {
		int n = grid.length;
		int[][] f = new int[n + 1][n + 1];
		for (int[] r : f) {
			Arrays.fill(r, Integer.MIN_VALUE);
		}
		f[1][1] = grid[0][0];
		for (int t = 1; t < n * 2 - 1; t++) {
			for (int j = Math.min(t, n - 1); j >= Math.max(t - n + 1, 0); j--) {
				for (int k = Math.min(t, n - 1); k >= j; k--) {
					if (grid[t - j][j] < 0 || grid[t - k][k] < 0) {
						f[j + 1][k + 1] = Integer.MIN_VALUE;
					} else {
						f[j + 1][k + 1] = Math.max(Math.max(f[j + 1][k + 1], f[j + 1][k]), Math.max(f[j][k + 1], f[j][k])) +
								grid[t - j][j] + (k != j ? grid[t - k][k] : 0);
					}
				}
			}
		}
		return Math.max(f[n][n], 0);
	}



}
//leetcode submit region end(Prohibit modification and deletion)

}
